package com.zjsru.plan2023.oneday;

import java.util.PriorityQueue;

/**
 * @Author: cookLee
 * @Date: 2023-10-29
 * 从数量最多的堆取走礼物
 */
public class PickGifts {

    /**
     * 主
     * \
     * 输入：gifts = [25,64,9,4,100], k = 4
     * 输出：29
     * 解释：
     * 按下述方式取走礼物：
     * - 在第一秒，选中最后一堆，剩下 10 个礼物。
     * - 接着第二秒选中第二堆礼物，剩下 8 个礼物。
     * - 然后选中第一堆礼物，剩下 5 个礼物。
     * - 最后，再次选中最后一堆礼物，剩下 3 个礼物。
     * 最后剩下的礼物数量分别是 [5,8,9,4,3] ，所以，剩下礼物的总数量是 29 。
     * \
     * 输入：gifts = [1,1,1,1], k = 4
     * 输出：4
     * 解释：
     * 在本例中，不管选中哪一堆礼物，都必须剩下 1 个礼物。
     * 也就是说，你无法获取任一堆中的礼物。
     * 所以，剩下礼物的总数量是 4 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        PickGifts pickGifts = new PickGifts();
        int[] gifts = new int[]{25,64,9,4,100};
        int k = 4;
        System.out.println(pickGifts.pickGifts(gifts, k));
    }

    /**
     * 优先队列
     *
     * @param gifts 礼物
     * @param k     k
     * @return long
     */
    public long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int num : gifts) {
            pq.offer(num);
        }
        while (k > 0) {
            Integer number = pq.poll();
            pq.offer((int) Math.sqrt(number));
            k--;
        }
        long ans = 0;
        while (!pq.isEmpty()) {
            ans += (long) pq.poll();
        }
        return ans;
    }

}
